1. Field of the Invention
The present invention relates to the field of computer system arbitration. More particularly, the present invention relates to an arbitration circuit that provides fair arbitration between a number of requestors and that provides input/output (I/O) to allow hierarchical cascading.
2. Related Art
The bus architecture of a computer system substantially influences the manner in which information is communicated between the components of a computer system. In a typical computer system, one or more buses are used to connect a central processing unit (CPU) to a memory and to input/output elements. Typically, the bus consists of several “lines” of electrically conductive material. The bus permits electrical signals representing data and control instructions to be readily transmitted between different components coupled to the bus. The order and speed at which the components interact with each other over the bus has a substantial impact on the performance of the computer system.
In accordance with industry standard, only one data transaction can take place on a bus at any given time. To ensure this requirement is enforced, the typical bus system has an arbiter that controls access to the bus. When an agent or device wishes use of the bus to transmit or receive data, the agent requests bus “ownership” from the arbiter. The agent requesting ownership is referred to as an initiator agent or master device. The term master device is generally used throughout all bus systems. The agent with whom the initiator agent is attempting to communicate is referred to as a target agent or slave device. The term slave device is used generally throughout all bus systems.
Typically, each of the agents or devices may independently act as an initiator and request bus ownership. Thus, at any given time several of the agents may be requesting bus ownership simultaneously. Where there are simultaneous requests for bus ownership, an arbiter is employed to arbitrate among requesting initiator agents, or master devices, to determine which one may be granted bus ownership.
In the case of typical arbitration, a priority system is set up. Each device wishes ownership of the bus in accordance with its respective requirements. These requirements may include, for example, latency tolerance, data transfer bandwidth, block transfer size, and the like. Each device should have a differing priority status with regard to their respective requests for bus ownership. Some devices are more critical to the proper operation of the computer system than others, some are less tolerant of latency than others, and some devices need to transfer very large quantities of data. If the arbiter grants access in an erratic or arbitrary manner, there is no assurance that the computer system will operate effectively. However, if devices with more critical requirements are assured a better chance of obtaining bus access, the computer system will operate more efficiently. Thus, the order in which master devices access a bus is very important and often critical to the optimal operation of the computer system. Typically, the order in which devices access a bus is set forth in an arbitration priority scheme.
Despite the potential benefits of a priority arbitration system, it has several flaws. When any other device requests bus ownership simultaneously with another device, the device with highest priority always wins and receives ownership first. Lower priority devices may not be granted sufficient access to the bus because they can be prevented from acquiring ownership for long periods of time. That is, lower priority devices may be “starved” of bus access, especially in a system where there are many high priority devices. Hence, a priority arbitration scheme does not ensure low priority devices may be granted adequate bus access.
Given that the priority arbitration scheme is typically based on the respective requirements of devices in the computer system, the most efficient arbitration priority arbitration scheme is not ascertainable until after the devices of a particular computer system are designed and their requirements ascertained. Previously, an optimal design for the PCI arbiter could not be accomplished until after the master devices and slave devices of a particular computer system were designed. Thus, engineering resources committed to the arbiter design are essentially “on hold” until after the rest of the computer system is designed. In addition, waiting to design the arbiter means that there are significant delays in production of the final product and in realizing the advantages associated with new computer designs.
Other arbitration schemes, such as “round robin” schemes, in which access is granted on a rotating, first-come, first-served basis, exist. The round robin scheme is usually best used in a system where all master devices perform tasks that are of equal priority and in which the servicing of events can be arbitrarily started and stopped without a problem. Each of the existing schemes has its advantages and disadvantages, depending on application.
As chip designs evolve and the number of transistors on a chip increases, whole systems are being designed on a single chip. Most processing elements in a system-on-a-chip communicate with each other via buses and memory. As the number of bus masters increases and fluctuates in a single chip, powerful arbitration that is efficient and scalable is becoming of greater and greater importance.